#include <bits/stdc++.h>
#define endl '\n'
#define PII pair<int, int>
#define int long long
using namespace std;
const int N = 1e6 + 100;
int t, a[N];
int n;
struct color{
	int id, res;
} tong[N];
bool cmp(color x, color y){
	return x.res > y.res;
}
void read (int &x){
	int res = 0;
	char c;
	while (c = getchar()){
		if (c == ' ' || c == '\n'){
            x = res;
			return ;
		}
		res = res * 10 + (int)(c - '0');
	}
}
void write (int x){
	cout << x;
	return ;
}
int sum = 0;
void digui(int left1, int right1){
	// cout << left1 << ' ' << right1 << ' ' << sum << endl;
	if (left1 >= right1){
		return ;
	}
	for (int i = 1; i <= 1000000; i++){
		tong[i].res = 0;
	}
	for (int i = left1; i <= right1; i++){
		tong[a[i]].res++;
		// tong[a[i]].id = a[i];
	}
	int cnt = -1, l = 0, r, id;
	sort (tong + left1, tong + right1 + 1, cmp);
    if (tong[1].res == 1){
        return ;
    }
	for (int i = 1; i <= 1000000; i++){
		if (tong[i].res == 0){
			break;
		}
		if (tong[i].res * tong[i].id >= cnt){
			cnt = tong[i].res * (tong[i].id - 1);
			id = i;
		}
	}

	for (int i = 1; i <= n; i++){
		if (id == a[i]){
			r = i;
		}
		if (id == a[i] && l == 0){
			l = i;
		}
	}
	sum += cnt;
	digui(1, l - 1);
	digui(r + 1, n);
}
void solve(){
	for (int i = 1; i <= 1000000; i++){
		tong[i].id = i;
	}
	read(n);
	for (int i = 1; i <= n; i++){
		read(a[i]);
	}
	digui(1, n);
	cout << sum << endl;
}
signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	freopen ("color.in", "r", stdin);
	freopen ("color.out", "w", stdout);
	read(t);
	while (t--){
		solve();
	}
	return 0;
}
